We present a novel, highly efficient algorithm to parallelize O(N^2) direct summation method for N-body problems with individual timesteps on distributed-memory parallel machines such as Beowulf clusters. Previously known algorithms, in which all processors have complete copies of the N-body system, has the serious problem that the communication-computation ratio increases as we increase the number of processors, since the communication cost is independent of the number of processors. In the new algorithm, p processors are organized as a $\sqrt{p}\times \sqrt{p}$ two-dimensional array. Each processor has $N/\sqrt{p}$ particles, but the data are distributed in such a way that complete system is presented if we look at any row or column consisting of $\sqrt{p}$ processors. In this algorithm, the communication cost scales as $N /\sqrt{p}$, while the calculation cost scales as $N^2/p$. Thus, we can use a much larger number of processors without losing efficiency compared to what was practical with previously known algorithms.
展开▼
机译：我们提出了一种新颖的，高效的算法，用于在分布式内存并行机（例如Beowulf集群）上对具有各个时间步长的N体问题的O（N ^ 2）直接求和方法进行并行化。其中所有处理器具有N体系统的完整副本的先前已知算法具有严重的问题，即通信成本随我们增加处理器数量而增加，因为通信成本与处理器数量无关。在新算法中，p个处理器被组织为$ \ sqrt {p} \ times \ sqrt {p} $二维数组。每个处理器都有$ N / \ sqrt {p} $个粒子，但是如果我们查看由$ \ sqrt {p} $个处理器组成的任何行或列，则数据的分布方式将显示完整的系统。在该算法中，通信成本缩放为$ N / \ sqrt {p} $，而计算成本缩放为$ N ^ 2 / p $。因此，与以前已知的算法相比，我们可以使用更多数量的处理器而不会降低效率。
展开▼
